package suanfa;

public class binarySearch {
//    i<=j意味者区间之内有未比较的元素，当查找的目标就是i和j指向的值时用=
//
//            （i+j）/2，如果i和j都很大，超过规定范围会把第一位看作符号位，改用>>>符号可以避免
    public static int Search(int[] a, int target){
        int i = 0;
        int j = a.length-1;
        while (i <= j){
            int m = (i+j) >>> 1;
            if (target > a[m]){
                i = m+1;
            } else if (target < a[m]) {
                j = m-1;
            }else {
                return m;
            }
        }
        return -1;
    }
    //j是范围外的，看作j作角标时一定不会取到
    public static int Search2(int[] a, int target){
        int i = 0;
        int j = a.length;
        while (i<j){
            int m = (i+j)>>>1;
            if (target > a[m]){
                i = m+1;
            } else if (target < a[m]) {
                j = m;
            }else {
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ints = {2, 4, 8, 10, 11};
        System.out.println(Search2(ints, 8));
    }
}
